package class30_bfprt_reservoir;

public class ReservoirSampling {
    public static int[] rs(int x, int k){
        int[] ans = new int[k];
        for(int i=0;i<x;i++){
            if(i<k){
                ans[i] = i;
            }
            else{
                if((double)k/(double)(i+1) >= Math.random()){//由于从0开始所以要+1
                    ans[(int)(Math.random()*k)]=i;
                }
            }
        }
        return ans;
    }

    public static void test(int x, int k, int time){
        int[] counter = new int[x];
        for(int i=0; i<time; i++){
            int[] ans = rs(x,k);
            for(int j=0; j<ans.length; j++) {
                counter[ans[j]]++;
            }
        }
        for(int i=0;i<counter.length;i++){
            System.out.println(i+" "+counter[i]);
        }
    }

    public static void main(String[] args) {
        test(50,17,1000);
    }
}
